<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.17"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>My Project: BTree.h Source File</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td id="projectalign" style="padding-left: 0.5em;">
   <div id="projectname">My Project
   </div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.17 -->
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
var searchBox = new SearchBox("searchBox", "search",false,'Search');
/* @license-end */
</script>
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
$(function() {
  initMenu('',true,false,'search.php','Search');
  $(document).ready(function() { init_search(); });
});
/* @license-end */</script>
<div id="main-nav"></div>
</div><!-- top -->
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div class="header">
  <div class="headertitle">
<div class="title">BTree.h</div>  </div>
</div><!--header-->
<div class="contents">
<a href="BTree_8h.html">Go to the documentation of this file.</a><div class="fragment"><div class="line"><a name="l00001"></a><span class="lineno">    1</span>&#160;<span class="preprocessor">#ifndef BTREE_H</span></div>
<div class="line"><a name="l00002"></a><span class="lineno">    2</span>&#160;<span class="preprocessor">#define BTREE_H</span></div>
<div class="line"><a name="l00003"></a><span class="lineno">    3</span>&#160;<span class="preprocessor">#define DEBUG</span></div>
<div class="line"><a name="l00004"></a><span class="lineno">    4</span>&#160; </div>
<div class="line"><a name="l00014"></a><span class="lineno">   14</span>&#160;<span class="preprocessor">#include &lt;cstdio&gt;</span></div>
<div class="line"><a name="l00015"></a><span class="lineno">   15</span>&#160;<span class="preprocessor">#include &lt;memory&gt;</span></div>
<div class="line"><a name="l00016"></a><span class="lineno">   16</span>&#160; </div>
<div class="line"><a name="l00017"></a><span class="lineno">   17</span>&#160;<span class="preprocessor">#include &quot;vector/vector.h&quot;</span></div>
<div class="line"><a name="l00018"></a><span class="lineno">   18</span>&#160; </div>
<div class="line"><a name="l00025"></a><span class="lineno">   25</span>&#160;<span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;</div>
<div class="line"><a name="l00026"></a><span class="lineno"><a class="line" href="classBTree.html">   26</a></span>&#160;<span class="keyword">class </span><a class="code" href="classBTree.html">BTree</a> {</div>
<div class="line"><a name="l00027"></a><span class="lineno">   27</span>&#160;   <span class="keyword">private</span>:</div>
<div class="line"><a name="l00028"></a><span class="lineno">   28</span>&#160;    <span class="keyword">struct </span>BTNode;</div>
<div class="line"><a name="l00029"></a><span class="lineno">   29</span>&#160; </div>
<div class="line"><a name="l00030"></a><span class="lineno">   30</span>&#160;   <span class="keyword">public</span>:</div>
<div class="line"><a name="l00031"></a><span class="lineno">   31</span>&#160;    <span class="keyword">using</span> BTNodePtr = std::unique_ptr&lt;BTNode&gt;;</div>
<div class="line"><a name="l00032"></a><span class="lineno">   32</span>&#160;    <span class="keyword">using</span> BTNodePosi = BTNode*;</div>
<div class="line"><a name="l00033"></a><span class="lineno">   33</span>&#160; </div>
<div class="line"><a name="l00034"></a><span class="lineno">   34</span>&#160;   <span class="keyword">private</span>:</div>
<div class="line"><a name="l00035"></a><span class="lineno">   35</span>&#160;    <span class="keyword">struct </span>BTNode {</div>
<div class="line"><a name="l00036"></a><span class="lineno">   36</span>&#160;        BTNode(<span class="keyword">const</span> BTNode&amp;) = <span class="keyword">delete</span>;</div>
<div class="line"><a name="l00037"></a><span class="lineno">   37</span>&#160;        BTNode&amp; operator=(<span class="keyword">const</span> BTNode&amp;) = <span class="keyword">delete</span>;</div>
<div class="line"><a name="l00038"></a><span class="lineno">   38</span>&#160;        <span class="comment">// 无关键码结点, 会创建一个空节点儿子</span></div>
<div class="line"><a name="l00039"></a><span class="lineno">   39</span>&#160;        BTNode() : parent(<span class="keyword">nullptr</span>) { child.emplace_back(<span class="keyword">nullptr</span>); }</div>
<div class="line"><a name="l00040"></a><span class="lineno">   40</span>&#160;        <span class="comment">// 一个关键码，且作为根结点</span></div>
<div class="line"><a name="l00041"></a><span class="lineno">   41</span>&#160;        BTNode(<span class="keyword">const</span> T&amp; e, BTNodePtr&amp;&amp; lc = <span class="keyword">nullptr</span>, BTNodePtr&amp;&amp; rc = <span class="keyword">nullptr</span>)</div>
<div class="line"><a name="l00042"></a><span class="lineno">   42</span>&#160;            : parent(<span class="keyword">nullptr</span>), key{e}</div>
<div class="line"><a name="l00043"></a><span class="lineno">   43</span>&#160;        {</div>
<div class="line"><a name="l00044"></a><span class="lineno">   44</span>&#160;            <span class="keywordflow">if</span> (lc != <span class="keyword">nullptr</span>) lc-&gt;parent = <span class="keyword">this</span>;</div>
<div class="line"><a name="l00045"></a><span class="lineno">   45</span>&#160;            <span class="keywordflow">if</span> (rc != <span class="keyword">nullptr</span>) rc-&gt;parent = <span class="keyword">this</span>;</div>
<div class="line"><a name="l00046"></a><span class="lineno">   46</span>&#160;            child.push_back(std::move(lc));</div>
<div class="line"><a name="l00047"></a><span class="lineno">   47</span>&#160;            child.push_back(std::move(rc));</div>
<div class="line"><a name="l00048"></a><span class="lineno">   48</span>&#160;        }</div>
<div class="line"><a name="l00049"></a><span class="lineno">   49</span>&#160; </div>
<div class="line"><a name="l00050"></a><span class="lineno">   50</span>&#160;        BTNodePosi parent;        <span class="comment">// 父节点</span></div>
<div class="line"><a name="l00051"></a><span class="lineno">   51</span>&#160;        Vector&lt;T&gt; key;            <span class="comment">//关键码向量</span></div>
<div class="line"><a name="l00052"></a><span class="lineno">   52</span>&#160;        Vector&lt;BTNodePtr&gt; child;  <span class="comment">// 孩子向量</span></div>
<div class="line"><a name="l00053"></a><span class="lineno">   53</span>&#160;    };</div>
<div class="line"><a name="l00054"></a><span class="lineno">   54</span>&#160; </div>
<div class="line"><a name="l00055"></a><span class="lineno">   55</span>&#160;   <span class="keyword">public</span>:</div>
<div class="line"><a name="l00061"></a><span class="lineno"><a class="line" href="classBTree.html#a9fc26aa50dd71d0892fe79a5e4fc7db7">   61</a></span>&#160;    <a class="code" href="classBTree.html#a9fc26aa50dd71d0892fe79a5e4fc7db7">BTree</a>(<span class="keywordtype">int</span> order = 3) : size_(0), order_(order), root_(std::make_unique&lt;BTNode&gt;()), hot_(nullptr)</div>
<div class="line"><a name="l00062"></a><span class="lineno">   62</span>&#160;    {</div>
<div class="line"><a name="l00063"></a><span class="lineno">   63</span>&#160;    }</div>
<div class="line"><a name="l00064"></a><span class="lineno">   64</span>&#160;    <span class="comment">// 对象语义，显式删去copy，移动的保留</span></div>
<div class="line"><a name="l00065"></a><span class="lineno">   65</span>&#160;    <a class="code" href="classBTree.html#a9fc26aa50dd71d0892fe79a5e4fc7db7">BTree</a>(<span class="keyword">const</span> <a class="code" href="classBTree.html">BTree</a>&amp;) = <span class="keyword">delete</span>;</div>
<div class="line"><a name="l00066"></a><span class="lineno">   66</span>&#160;    <a class="code" href="classBTree.html">BTree</a>&amp; operator=(<span class="keyword">const</span> <a class="code" href="classBTree.html">BTree</a>&amp;) = <span class="keyword">delete</span>;</div>
<div class="line"><a name="l00067"></a><span class="lineno">   67</span>&#160;    <span class="keywordtype">int</span> order()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> order_; }</div>
<div class="line"><a name="l00068"></a><span class="lineno">   68</span>&#160;    <span class="keywordtype">int</span> size()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> size_; }</div>
<div class="line"><a name="l00069"></a><span class="lineno">   69</span>&#160;    <span class="keywordtype">bool</span> empty()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> root_ == <span class="keyword">nullptr</span>; }</div>
<div class="line"><a name="l00070"></a><span class="lineno">   70</span>&#160;    BTNodePosi root()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> root_.get(); }  <span class="comment">//调试用</span></div>
<div class="line"><a name="l00071"></a><span class="lineno">   71</span>&#160;    BTNodePosi <a class="code" href="classBTree.html#abef4d3b58f15a705a8160360d2cd60ec">search</a>(<span class="keyword">const</span> T&amp; e);</div>
<div class="line"><a name="l00072"></a><span class="lineno">   72</span>&#160;    <span class="keywordtype">bool</span> <a class="code" href="classBTree.html#ad0a275883210c05d4af1644f45128f18">insert</a>(<span class="keyword">const</span> T&amp; e);</div>
<div class="line"><a name="l00073"></a><span class="lineno">   73</span>&#160;    <span class="keywordtype">bool</span> <a class="code" href="classBTree.html#aff6835ad66ba5115ae28b2c21b328f51">remove</a>(<span class="keyword">const</span> T&amp; e);</div>
<div class="line"><a name="l00074"></a><span class="lineno">   74</span>&#160; </div>
<div class="line"><a name="l00075"></a><span class="lineno">   75</span>&#160;   <span class="keyword">private</span>:</div>
<div class="line"><a name="l00076"></a><span class="lineno">   76</span>&#160;    <span class="keywordtype">void</span> solveOverflow(BTNodePosi);   <span class="comment">// 因插入而上溢之后的分裂处理</span></div>
<div class="line"><a name="l00077"></a><span class="lineno">   77</span>&#160;    <span class="keywordtype">void</span> solveUnderflow(BTNodePosi);  <span class="comment">// 因下溢之后的合并处理</span></div>
<div class="line"><a name="l00078"></a><span class="lineno">   78</span>&#160;   <span class="keyword">private</span>:</div>
<div class="line"><a name="l00079"></a><span class="lineno">   79</span>&#160;    <span class="keywordtype">int</span> size_;   <span class="comment">//关键码总数</span></div>
<div class="line"><a name="l00080"></a><span class="lineno">   80</span>&#160;    <span class="keywordtype">int</span> order_;  <span class="comment">// B-树的阶次，至少为3，一般不能修改</span></div>
<div class="line"><a name="l00081"></a><span class="lineno">   81</span>&#160;    BTNodePtr root_;</div>
<div class="line"><a name="l00082"></a><span class="lineno">   82</span>&#160;    BTNodePosi hot_;  <span class="comment">// BTree::search()最后访问的非空（除非树空）结点的位置</span></div>
<div class="line"><a name="l00083"></a><span class="lineno">   83</span>&#160;};</div>
<div class="line"><a name="l00084"></a><span class="lineno">   84</span>&#160; </div>
<div class="line"><a name="l00092"></a><span class="lineno">   92</span>&#160;<span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;</div>
<div class="line"><a name="l00093"></a><span class="lineno"><a class="line" href="classBTree.html#abef4d3b58f15a705a8160360d2cd60ec">   93</a></span>&#160;<span class="keyword">typename</span> BTree&lt;T&gt;::BTNodePosi <a class="code" href="classBTree.html#abef4d3b58f15a705a8160360d2cd60ec">BTree&lt;T&gt;::search</a>(<span class="keyword">const</span> T&amp; e)</div>
<div class="line"><a name="l00094"></a><span class="lineno">   94</span>&#160;{</div>
<div class="line"><a name="l00095"></a><span class="lineno">   95</span>&#160;    <span class="keyword">auto</span> v{root_.get()};</div>
<div class="line"><a name="l00096"></a><span class="lineno">   96</span>&#160;    hot_ = <span class="keyword">nullptr</span>;  <span class="comment">//从根节点出发</span></div>
<div class="line"><a name="l00097"></a><span class="lineno">   97</span>&#160;    <span class="keywordflow">while</span> (v != <span class="keyword">nullptr</span>) {</div>
<div class="line"><a name="l00098"></a><span class="lineno">   98</span>&#160;        <span class="comment">// 找到 &lt;= e的最大值的下标</span></div>
<div class="line"><a name="l00099"></a><span class="lineno">   99</span>&#160;        Rank searchPos = v-&gt;key.search(e);</div>
<div class="line"><a name="l00100"></a><span class="lineno">  100</span>&#160;        <span class="keywordflow">if</span> (searchPos &gt;= 0 &amp;&amp; v-&gt;key[searchPos] == e) <span class="keywordflow">return</span> v;</div>
<div class="line"><a name="l00101"></a><span class="lineno">  101</span>&#160;        hot_ = v;  <span class="comment">// 最后访问的非空（除非树空）结点的位置</span></div>
<div class="line"><a name="l00102"></a><span class="lineno">  102</span>&#160;        v = v-&gt;child[searchPos + 1].get();  <span class="comment">// 转入对应子树</span></div>
<div class="line"><a name="l00103"></a><span class="lineno">  103</span>&#160;    }</div>
<div class="line"><a name="l00104"></a><span class="lineno">  104</span>&#160;    <span class="keywordflow">return</span> <span class="keyword">nullptr</span>;  <span class="comment">// 失败，返回外部结点</span></div>
<div class="line"><a name="l00105"></a><span class="lineno">  105</span>&#160;}</div>
<div class="line"><a name="l00114"></a><span class="lineno">  114</span>&#160;<span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;</div>
<div class="line"><a name="l00115"></a><span class="lineno"><a class="line" href="classBTree.html#ad0a275883210c05d4af1644f45128f18">  115</a></span>&#160;<span class="keywordtype">bool</span> <a class="code" href="classBTree.html#ad0a275883210c05d4af1644f45128f18">BTree&lt;T&gt;::insert</a>(<span class="keyword">const</span> T&amp; e)</div>
<div class="line"><a name="l00116"></a><span class="lineno">  116</span>&#160;{</div>
<div class="line"><a name="l00117"></a><span class="lineno">  117</span>&#160;    <span class="keyword">auto</span> v{this-&gt;search(e)};</div>
<div class="line"><a name="l00118"></a><span class="lineno">  118</span>&#160;    <span class="keywordflow">if</span> (v != <span class="keyword">nullptr</span>) <span class="keywordflow">return</span> <span class="keyword">false</span>;  <span class="comment">// 不能重复插入</span></div>
<div class="line"><a name="l00119"></a><span class="lineno">  119</span>&#160;    <span class="keyword">auto</span> r{hot_-&gt;key.search(e)};  <span class="comment">// hot_是叶子结点，在这个向量上找到合适的位置</span></div>
<div class="line"><a name="l00120"></a><span class="lineno">  120</span>&#160;    hot_-&gt;key.insert(r + 1, e);   <span class="comment">//将新关键码插至对应的位置</span></div>
<div class="line"><a name="l00121"></a><span class="lineno">  121</span>&#160;    hot_-&gt;child.insert(r + 2, <span class="keyword">nullptr</span>);  <span class="comment">// 新外部结点</span></div>
<div class="line"><a name="l00122"></a><span class="lineno">  122</span>&#160;    ++size_;</div>
<div class="line"><a name="l00123"></a><span class="lineno">  123</span>&#160;    solveOverflow(hot_);  <span class="comment">// 如有必要，需要分裂</span></div>
<div class="line"><a name="l00124"></a><span class="lineno">  124</span>&#160;    <span class="keywordflow">return</span> <span class="keyword">true</span>;</div>
<div class="line"><a name="l00125"></a><span class="lineno">  125</span>&#160;}</div>
<div class="line"><a name="l00135"></a><span class="lineno">  135</span>&#160;<span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;</div>
<div class="line"><a name="l00136"></a><span class="lineno">  136</span>&#160;<span class="keywordtype">void</span> <a class="code" href="classBTree.html">BTree&lt;T&gt;::solveOverflow</a>(BTNodePosi v)</div>
<div class="line"><a name="l00137"></a><span class="lineno">  137</span>&#160;{</div>
<div class="line"><a name="l00138"></a><span class="lineno">  138</span>&#160;    <span class="keywordflow">if</span> (order_ &gt;= v-&gt;child.size()) <span class="keywordflow">return</span>;  <span class="comment">//未上溢</span></div>
<div class="line"><a name="l00139"></a><span class="lineno">  139</span>&#160;    Rank s = order_ / 2;                    <span class="comment">//中位数的位置</span></div>
<div class="line"><a name="l00140"></a><span class="lineno">  140</span>&#160;    <span class="keyword">auto</span> u{std::make_unique&lt;BTNode&gt;()};     <span class="comment">// u有一个空节点  是左儿子</span></div>
<div class="line"><a name="l00141"></a><span class="lineno">  141</span>&#160;    <span class="comment">// 移动v的从s + 1开始的结点 给u</span></div>
<div class="line"><a name="l00142"></a><span class="lineno">  142</span>&#160;    u-&gt;key.<a class="code" href="classBTree.html#ad0a275883210c05d4af1644f45128f18">insert</a>(u-&gt;key.begin(), std::make_move_iterator(v-&gt;key.begin() + s + 1),</div>
<div class="line"><a name="l00143"></a><span class="lineno">  143</span>&#160;                  std::make_move_iterator(v-&gt;key.end()));</div>
<div class="line"><a name="l00144"></a><span class="lineno">  144</span>&#160;    u-&gt;child.pop_back();  <span class="comment">// 这里要重点注意！nullptr是要被覆盖掉的</span></div>
<div class="line"><a name="l00145"></a><span class="lineno">  145</span>&#160;    u-&gt;child.insert(u-&gt;child.begin(), std::make_move_iterator(v-&gt;child.begin() + s + 1),</div>
<div class="line"><a name="l00146"></a><span class="lineno">  146</span>&#160;                    std::make_move_iterator(v-&gt;child.end()));</div>
<div class="line"><a name="l00147"></a><span class="lineno">  147</span>&#160;    v-&gt;key.resize(s + 1);  <span class="comment">//后面会再pop_back(中位数)一次</span></div>
<div class="line"><a name="l00148"></a><span class="lineno">  148</span>&#160;    v-&gt;child.resize(s + 1);</div>
<div class="line"><a name="l00149"></a><span class="lineno">  149</span>&#160;    <span class="comment">//因为insert过的点，必然是从front开始的，所以只用检测front即可判断孩子们是否非空</span></div>
<div class="line"><a name="l00150"></a><span class="lineno">  150</span>&#160;    <span class="keywordflow">if</span> (u-&gt;child.front() != <span class="keyword">nullptr</span>)  <span class="comment">// 令u的孩子们 指向u</span></div>
<div class="line"><a name="l00151"></a><span class="lineno">  151</span>&#160;        <span class="keywordflow">for</span> (<span class="keyword">const</span> <span class="keyword">auto</span>&amp; child : u-&gt;child) child-&gt;parent = u.get();</div>
<div class="line"><a name="l00152"></a><span class="lineno">  152</span>&#160; </div>
<div class="line"><a name="l00153"></a><span class="lineno">  153</span>&#160;    BTNodePosi father{v-&gt;parent};</div>
<div class="line"><a name="l00154"></a><span class="lineno">  154</span>&#160; </div>
<div class="line"><a name="l00155"></a><span class="lineno">  155</span>&#160;    <span class="keywordflow">if</span> (father == <span class="keyword">nullptr</span>) {                        <span class="comment">// v是根结点</span></div>
<div class="line"><a name="l00156"></a><span class="lineno">  156</span>&#160;        <span class="keyword">auto</span> newRoot{std::make_unique&lt;BTNode&gt;()};   <span class="comment">// 创建新的根节点</span></div>
<div class="line"><a name="l00157"></a><span class="lineno">  157</span>&#160;        father = newRoot.get();                     <span class="comment">// 重新设置father</span></div>
<div class="line"><a name="l00158"></a><span class="lineno">  158</span>&#160;        v-&gt;parent = father;                         <span class="comment">// v的parent 指向 新根</span></div>
<div class="line"><a name="l00159"></a><span class="lineno">  159</span>&#160;        newRoot-&gt;child.front() = std::move(root_);  <span class="comment">// 新根的子节点 是原来的root_</span></div>
<div class="line"><a name="l00160"></a><span class="lineno">  160</span>&#160;        root_ = std::move(newRoot);                 <span class="comment">// 换根</span></div>
<div class="line"><a name="l00161"></a><span class="lineno">  161</span>&#160;    }</div>
<div class="line"><a name="l00162"></a><span class="lineno">  162</span>&#160;    Rank r = 1 + father-&gt;key.search(v-&gt;key.front());  <span class="comment">// 找到最大的&lt;=key[0]的位置+1插入key[s]</span></div>
<div class="line"><a name="l00163"></a><span class="lineno">  163</span>&#160;    father-&gt;key.insert(r, std::move(v-&gt;key.back()));  <span class="comment">// 轴点关键码上升</span></div>
<div class="line"><a name="l00164"></a><span class="lineno">  164</span>&#160;    v-&gt;key.pop_back();                                <span class="comment">// v删去中位数这个结点</span></div>
<div class="line"><a name="l00165"></a><span class="lineno">  165</span>&#160;    u-&gt;parent = father;                               <span class="comment">// 新儿子u与父节点p互联</span></div>
<div class="line"><a name="l00166"></a><span class="lineno">  166</span>&#160;    father-&gt;child.insert(r + 1, std::move(u));        <span class="comment">// father连上新儿子</span></div>
<div class="line"><a name="l00167"></a><span class="lineno">  167</span>&#160;    solveOverflow(father);  <span class="comment">//上升一层，如有必要则继续分裂——至多递归O(logn)层</span></div>
<div class="line"><a name="l00168"></a><span class="lineno">  168</span>&#160;}</div>
<div class="line"><a name="l00169"></a><span class="lineno">  169</span>&#160; </div>
<div class="line"><a name="l00178"></a><span class="lineno">  178</span>&#160;<span class="keyword">template</span> &lt;<span class="keyword">typename</span> T&gt;</div>
<div class="line"><a name="l00179"></a><span class="lineno"><a class="line" href="classBTree.html#aff6835ad66ba5115ae28b2c21b328f51">  179</a></span>&#160;<span class="keywordtype">bool</span> <a class="code" href="classBTree.html#aff6835ad66ba5115ae28b2c21b328f51">BTree&lt;T&gt;::remove</a>(<span class="keyword">const</span> T&amp; e)</div>
<div class="line"><a name="l00180"></a><span class="lineno">  180</span>&#160;{</div>
<div class="line"><a name="l00181"></a><span class="lineno">  181</span>&#160;    BTNodePosi v{search(e)};</div>
<div class="line"><a name="l00182"></a><span class="lineno">  182</span>&#160;    <span class="keywordflow">if</span> (v == <span class="keyword">nullptr</span>) <span class="keywordflow">return</span> <span class="keyword">false</span>;</div>
<div class="line"><a name="l00183"></a><span class="lineno">  183</span>&#160;    Rank r{v-&gt;key.search(e)};           <span class="comment">//确定目标关键码的秩</span></div>
<div class="line"><a name="l00184"></a><span class="lineno">  184</span>&#160;    <span class="keywordflow">if</span> (v-&gt;child.front() != <span class="keyword">nullptr</span>) {  <span class="comment">//若e非叶子节点，那么e的后继必属某叶节点</span></div>
<div class="line"><a name="l00185"></a><span class="lineno">  185</span>&#160;        BTNodePosi u{v-&gt;child[r + 1].get()};</div>
<div class="line"><a name="l00186"></a><span class="lineno">  186</span>&#160;        <span class="keywordflow">while</span> (u-&gt;child[0] != <span class="keyword">nullptr</span>) u = u-&gt;child[0].get();  <span class="comment">// 右子树一直往左</span></div>
<div class="line"><a name="l00187"></a><span class="lineno">  187</span>&#160;        v-&gt;key[r] = std::move(u-&gt;key[0]);  <span class="comment">// 换成最左边的key，也就是后继</span></div>
<div class="line"><a name="l00188"></a><span class="lineno">  188</span>&#160;        v = u;                             <span class="comment">// 因此u-&gt;key[0]将会被删去</span></div>
<div class="line"><a name="l00189"></a><span class="lineno">  189</span>&#160;        r = 0;</div>
<div class="line"><a name="l00190"></a><span class="lineno">  190</span>&#160;    }</div>
<div class="line"><a name="l00191"></a><span class="lineno">  191</span>&#160;    v-&gt;key.remove(r);        <span class="comment">// 删除关键码</span></div>
<div class="line"><a name="l00192"></a><span class="lineno">  192</span>&#160;    v-&gt;child.remove(r + 1);  <span class="comment">// 以及一个外部结点 ，这里也可以用pop_back,因为都是nullptr</span></div>
<div class="line"><a name="l00193"></a><span class="lineno">  193</span>&#160;    --size_;</div>
<div class="line"><a name="l00194"></a><span class="lineno">  194</span>&#160;    solveUnderflow(v);</div>
<div class="line"><a name="l00195"></a><span class="lineno">  195</span>&#160;    <span class="keywordflow">return</span> <span class="keyword">true</span>;</div>
<div class="line"><a name="l00196"></a><span class="lineno">  196</span>&#160;}</div>
<div class="line"><a name="l00197"></a><span class="lineno">  197</span>&#160; </div>
<div class="line"><a name="l00207"></a><span class="lineno">  207</span>&#160;<span class="keyword">template</span> &lt;<span class="keyword">typename</span> T&gt;  <span class="comment">//关键码删除后若节点下溢，则做节点旋转或合并处理</span></div>
<div class="line"><a name="l00208"></a><span class="lineno">  208</span>&#160;<span class="keywordtype">void</span> <a class="code" href="classBTree.html">BTree&lt;T&gt;::solveUnderflow</a>(BTNodePosi v)</div>
<div class="line"><a name="l00209"></a><span class="lineno">  209</span>&#160;{</div>
<div class="line"><a name="l00210"></a><span class="lineno">  210</span>&#160;    <span class="keywordflow">if</span> ((order_ + 1) / 2 &lt;= v-&gt;child.size()) <span class="keywordflow">return</span>;  <span class="comment">// v并没有下溢</span></div>
<div class="line"><a name="l00211"></a><span class="lineno">  211</span>&#160;    BTNodePosi parent{v-&gt;parent};</div>
<div class="line"><a name="l00212"></a><span class="lineno">  212</span>&#160;    <span class="keywordflow">if</span> (parent == <span class="keyword">nullptr</span>) {  <span class="comment">// v是根结点</span></div>
<div class="line"><a name="l00213"></a><span class="lineno">  213</span>&#160;        <span class="comment">// 此时到了根结点，并且根节点key为空，且有孩子，那么换根</span></div>
<div class="line"><a name="l00214"></a><span class="lineno">  214</span>&#160;        <span class="keywordflow">if</span> (!v-&gt;key.size() &amp;&amp; v-&gt;child[0] != <span class="keyword">nullptr</span>) {</div>
<div class="line"><a name="l00215"></a><span class="lineno">  215</span>&#160;            root_ = std::move(v-&gt;child[0]);  <span class="comment">// 原root_(v)会被销毁</span></div>
<div class="line"><a name="l00216"></a><span class="lineno">  216</span>&#160;            root_-&gt;parent = <span class="keyword">nullptr</span>;</div>
<div class="line"><a name="l00217"></a><span class="lineno">  217</span>&#160;<span class="preprocessor">#ifdef DEBUG</span></div>
<div class="line"><a name="l00218"></a><span class="lineno">  218</span>&#160;            printf(<span class="stringliteral">&quot;collapse\n&quot;</span>);</div>
<div class="line"><a name="l00219"></a><span class="lineno">  219</span>&#160;<span class="preprocessor">#endif</span></div>
<div class="line"><a name="l00220"></a><span class="lineno">  220</span>&#160;        }</div>
<div class="line"><a name="l00221"></a><span class="lineno">  221</span>&#160;        <span class="keywordflow">return</span>;</div>
<div class="line"><a name="l00222"></a><span class="lineno">  222</span>&#160;    }</div>
<div class="line"><a name="l00223"></a><span class="lineno">  223</span>&#160;<span class="preprocessor">#ifdef DEBUG</span></div>
<div class="line"><a name="l00224"></a><span class="lineno">  224</span>&#160;    printf(<span class="stringliteral">&quot; ... case 0\n&quot;</span>);</div>
<div class="line"><a name="l00225"></a><span class="lineno">  225</span>&#160;<span class="preprocessor">#endif</span></div>
<div class="line"><a name="l00226"></a><span class="lineno">  226</span>&#160;    <span class="comment">// 确定parent的第r个孩子是v</span></div>
<div class="line"><a name="l00227"></a><span class="lineno">  227</span>&#160;    Rank r = 0;</div>
<div class="line"><a name="l00228"></a><span class="lineno">  228</span>&#160;    <span class="keywordflow">while</span> (parent-&gt;child[r].get() != v) r++;</div>
<div class="line"><a name="l00229"></a><span class="lineno">  229</span>&#160;    <span class="comment">// 情况1：有左兄弟，尝试向左兄弟借关键码 ： 右旋</span></div>
<div class="line"><a name="l00230"></a><span class="lineno">  230</span>&#160;    <span class="keywordflow">if</span> (r &gt; 0) {</div>
<div class="line"><a name="l00231"></a><span class="lineno">  231</span>&#160;        BTNodePosi ls{parent-&gt;child[r - 1].get()};</div>
<div class="line"><a name="l00232"></a><span class="lineno">  232</span>&#160;        <span class="keywordflow">if</span> (ls-&gt;child.size() &gt; (order_ + 1) / 2) {  <span class="comment">// 左兄弟可以借</span></div>
<div class="line"><a name="l00233"></a><span class="lineno">  233</span>&#160;<span class="preprocessor">#ifdef DEBUG</span></div>
<div class="line"><a name="l00234"></a><span class="lineno">  234</span>&#160;            printf(<span class="stringliteral">&quot; ... case 1\n&quot;</span>);</div>
<div class="line"><a name="l00235"></a><span class="lineno">  235</span>&#160;<span class="preprocessor">#endif</span></div>
<div class="line"><a name="l00236"></a><span class="lineno">  236</span>&#160;            v-&gt;key.insert(0, std::move(parent-&gt;key[r - 1]));  <span class="comment">// parent给右孩子(v)</span></div>
<div class="line"><a name="l00237"></a><span class="lineno">  237</span>&#160;            parent-&gt;key[r - 1] = std::move(ls-&gt;key.back());  <span class="comment">// p拿到最后ls的最大的一个结点</span></div>
<div class="line"><a name="l00238"></a><span class="lineno">  238</span>&#160;            ls-&gt;key.pop_back();</div>
<div class="line"><a name="l00239"></a><span class="lineno">  239</span>&#160; </div>
<div class="line"><a name="l00240"></a><span class="lineno">  240</span>&#160;            v-&gt;child.insert(0, std::move(ls-&gt;child.back()));</div>
<div class="line"><a name="l00241"></a><span class="lineno">  241</span>&#160;            ls-&gt;child.pop_back();</div>
<div class="line"><a name="l00242"></a><span class="lineno">  242</span>&#160;            <span class="comment">// ls最右侧孩子，作为v的最左侧孩子</span></div>
<div class="line"><a name="l00243"></a><span class="lineno">  243</span>&#160;            <span class="keywordflow">if</span> (v-&gt;child[0] != <span class="keyword">nullptr</span>) v-&gt;child[0]-&gt;parent = v;</div>
<div class="line"><a name="l00244"></a><span class="lineno">  244</span>&#160;            <span class="keywordflow">return</span>;  <span class="comment">//右旋完成</span></div>
<div class="line"><a name="l00245"></a><span class="lineno">  245</span>&#160;        }</div>
<div class="line"><a name="l00246"></a><span class="lineno">  246</span>&#160;    }</div>
<div class="line"><a name="l00247"></a><span class="lineno">  247</span>&#160;    <span class="comment">// 情况2：向右兄弟借关键码，则v是左 ：左旋</span></div>
<div class="line"><a name="l00248"></a><span class="lineno">  248</span>&#160;    <span class="keywordflow">if</span> (r + 1 &lt; parent-&gt;child.size()) {</div>
<div class="line"><a name="l00249"></a><span class="lineno">  249</span>&#160;        BTNodePosi rs{parent-&gt;child[r + 1].get()};  <span class="comment">//右兄弟必存在</span></div>
<div class="line"><a name="l00250"></a><span class="lineno">  250</span>&#160;        <span class="keywordflow">if</span> (rs-&gt;child.size() &gt; (order_ + 1) / 2) {</div>
<div class="line"><a name="l00251"></a><span class="lineno">  251</span>&#160;<span class="preprocessor">#ifdef DEBUG</span></div>
<div class="line"><a name="l00252"></a><span class="lineno">  252</span>&#160;            printf(<span class="stringliteral">&quot; ... case 2\n&quot;</span>);</div>
<div class="line"><a name="l00253"></a><span class="lineno">  253</span>&#160;<span class="preprocessor">#endif</span></div>
<div class="line"><a name="l00254"></a><span class="lineno">  254</span>&#160;            <span class="comment">// 1. parent的最小的给v</span></div>
<div class="line"><a name="l00255"></a><span class="lineno">  255</span>&#160;            v-&gt;key.push_back(std::move(parent-&gt;key[r]));</div>
<div class="line"><a name="l00256"></a><span class="lineno">  256</span>&#160;            <span class="comment">// 2. rs的最小点给parent</span></div>
<div class="line"><a name="l00257"></a><span class="lineno">  257</span>&#160;            parent-&gt;key[r] = std::move(rs-&gt;key.front());</div>
<div class="line"><a name="l00258"></a><span class="lineno">  258</span>&#160;            rs-&gt;key.remove(0);</div>
<div class="line"><a name="l00259"></a><span class="lineno">  259</span>&#160;            <span class="comment">// 3. rs的最左侧孩子过继给v,作为v的最右侧孩子</span></div>
<div class="line"><a name="l00260"></a><span class="lineno">  260</span>&#160;            v-&gt;child.push_back(std::move(rs-&gt;child.front()));</div>
<div class="line"><a name="l00261"></a><span class="lineno">  261</span>&#160;            rs-&gt;child.remove(0);</div>
<div class="line"><a name="l00262"></a><span class="lineno">  262</span>&#160; </div>
<div class="line"><a name="l00263"></a><span class="lineno">  263</span>&#160;            <span class="keywordflow">if</span> (v-&gt;child.back() != <span class="keyword">nullptr</span>) v-&gt;child.back()-&gt;parent = v;</div>
<div class="line"><a name="l00264"></a><span class="lineno">  264</span>&#160;            <span class="keywordflow">return</span>;</div>
<div class="line"><a name="l00265"></a><span class="lineno">  265</span>&#160;        }</div>
<div class="line"><a name="l00266"></a><span class="lineno">  266</span>&#160;    }</div>
<div class="line"><a name="l00267"></a><span class="lineno">  267</span>&#160;    <span class="comment">// 情况3：左右兄弟要么为空，要么都不够，那么就合并</span></div>
<div class="line"><a name="l00268"></a><span class="lineno">  268</span>&#160;    <span class="keywordflow">if</span> (r &gt; 0) {  <span class="comment">//存在左兄弟，与左兄弟合并</span></div>
<div class="line"><a name="l00269"></a><span class="lineno">  269</span>&#160;<span class="preprocessor">#ifdef DEBUG</span></div>
<div class="line"><a name="l00270"></a><span class="lineno">  270</span>&#160;        printf(<span class="stringliteral">&quot; ... case 3L\n&quot;</span>);</div>
<div class="line"><a name="l00271"></a><span class="lineno">  271</span>&#160;<span class="preprocessor">#endif</span></div>
<div class="line"><a name="l00272"></a><span class="lineno">  272</span>&#160;        BTNodePosi ls{parent-&gt;child[r - 1].get()};         <span class="comment">// 左兄弟必存在</span></div>
<div class="line"><a name="l00273"></a><span class="lineno">  273</span>&#160;        ls-&gt;key.push_back(std::move(parent-&gt;key[r - 1]));  <span class="comment">// 将父节点key移动到左边</span></div>
<div class="line"><a name="l00274"></a><span class="lineno">  274</span>&#160;        parent-&gt;key.remove(r - 1);</div>
<div class="line"><a name="l00275"></a><span class="lineno">  275</span>&#160;        <span class="comment">// p的第r - 1个关键码转入ls，v不再是p的第r个孩子</span></div>
<div class="line"><a name="l00276"></a><span class="lineno">  276</span>&#160;        <span class="comment">// v剩余的关键码和孩子，全部转入ls</span></div>
<div class="line"><a name="l00277"></a><span class="lineno">  277</span>&#160;        ls-&gt;key.insert(ls-&gt;key.end(), std::make_move_iterator(v-&gt;key.begin()),</div>
<div class="line"><a name="l00278"></a><span class="lineno">  278</span>&#160;                       std::make_move_iterator(v-&gt;key.end()));</div>
<div class="line"><a name="l00279"></a><span class="lineno">  279</span>&#160;        <span class="keywordflow">for</span> (<span class="keyword">auto</span>&amp; child : v-&gt;child)</div>
<div class="line"><a name="l00280"></a><span class="lineno">  280</span>&#160;            <span class="keywordflow">if</span> (child != <span class="keyword">nullptr</span>) child-&gt;parent = ls;</div>
<div class="line"><a name="l00281"></a><span class="lineno">  281</span>&#160;        ls-&gt;child.insert(ls-&gt;child.end(), std::make_move_iterator(v-&gt;child.begin()),</div>
<div class="line"><a name="l00282"></a><span class="lineno">  282</span>&#160;                         std::make_move_iterator(v-&gt;child.end()));</div>
<div class="line"><a name="l00283"></a><span class="lineno">  283</span>&#160;<span class="preprocessor">#ifdef DEBUG</span></div>
<div class="line"><a name="l00284"></a><span class="lineno">  284</span>&#160;        printf(<span class="stringliteral">&quot;284 v_child_size %d\n&quot;</span>, ls-&gt;child.size());</div>
<div class="line"><a name="l00285"></a><span class="lineno">  285</span>&#160;        printf(<span class="stringliteral">&quot;285 child_parent %d\n&quot;</span>, parent-&gt;child.size());</div>
<div class="line"><a name="l00286"></a><span class="lineno">  286</span>&#160;<span class="preprocessor">#endif</span></div>
<div class="line"><a name="l00287"></a><span class="lineno">  287</span>&#160;        <span class="comment">// 删掉右结点v</span></div>
<div class="line"><a name="l00288"></a><span class="lineno">  288</span>&#160;        parent-&gt;child.remove(r);</div>
<div class="line"><a name="l00289"></a><span class="lineno">  289</span>&#160;    } <span class="keywordflow">else</span> {  <span class="comment">// 与右兄弟合并</span></div>
<div class="line"><a name="l00290"></a><span class="lineno">  290</span>&#160;<span class="preprocessor">#ifdef DEBUG</span></div>
<div class="line"><a name="l00291"></a><span class="lineno">  291</span>&#160;        printf(<span class="stringliteral">&quot; ... case 3R\n&quot;</span>);</div>
<div class="line"><a name="l00292"></a><span class="lineno">  292</span>&#160;<span class="preprocessor">#endif</span></div>
<div class="line"><a name="l00293"></a><span class="lineno">  293</span>&#160;        BTNodePosi rs{parent-&gt;child[r + 1].get()};  <span class="comment">//右兄弟必存在</span></div>
<div class="line"><a name="l00294"></a><span class="lineno">  294</span>&#160;        rs-&gt;key.insert(0, std::move(parent-&gt;key[r]));</div>
<div class="line"><a name="l00295"></a><span class="lineno">  295</span>&#160;        parent-&gt;key.remove(r);</div>
<div class="line"><a name="l00296"></a><span class="lineno">  296</span>&#160;<span class="preprocessor">#ifdef DEBUG</span></div>
<div class="line"><a name="l00297"></a><span class="lineno">  297</span>&#160;        printf(<span class="stringliteral">&quot;297vSize %d, rsSize %d\n&quot;</span>, v-&gt;child.size(), rs-&gt;child.size());</div>
<div class="line"><a name="l00298"></a><span class="lineno">  298</span>&#160;<span class="preprocessor">#endif</span></div>
<div class="line"><a name="l00299"></a><span class="lineno">  299</span>&#160;        <span class="comment">// v剩余的关键码和孩子，全部转入ls</span></div>
<div class="line"><a name="l00300"></a><span class="lineno">  300</span>&#160;        rs-&gt;key.insert(rs-&gt;key.begin(), std::make_move_iterator(v-&gt;key.begin()),</div>
<div class="line"><a name="l00301"></a><span class="lineno">  301</span>&#160;                       std::make_move_iterator(v-&gt;key.end()));</div>
<div class="line"><a name="l00302"></a><span class="lineno">  302</span>&#160;        <span class="keywordflow">for</span> (<span class="keyword">auto</span>&amp; child : v-&gt;child)</div>
<div class="line"><a name="l00303"></a><span class="lineno">  303</span>&#160;            <span class="keywordflow">if</span> (child != <span class="keyword">nullptr</span>) child-&gt;parent = rs;  <span class="comment">// 过继孩子</span></div>
<div class="line"><a name="l00304"></a><span class="lineno">  304</span>&#160; </div>
<div class="line"><a name="l00305"></a><span class="lineno">  305</span>&#160;        rs-&gt;child.insert(rs-&gt;child.begin(), std::make_move_iterator(v-&gt;child.begin()),</div>
<div class="line"><a name="l00306"></a><span class="lineno">  306</span>&#160;                         std::make_move_iterator(v-&gt;child.end()));</div>
<div class="line"><a name="l00307"></a><span class="lineno">  307</span>&#160;<span class="preprocessor">#ifdef DEBUG</span></div>
<div class="line"><a name="l00308"></a><span class="lineno">  308</span>&#160;        <span class="keywordflow">for</span> (<span class="keyword">auto</span> t : rs-&gt;key) printf(<span class="stringliteral">&quot;%d - ------- &quot;</span>, t);</div>
<div class="line"><a name="l00309"></a><span class="lineno">  309</span>&#160;        printf(<span class="stringliteral">&quot;\n&quot;</span>);</div>
<div class="line"><a name="l00310"></a><span class="lineno">  310</span>&#160;        <span class="comment">// 删掉左结点v</span></div>
<div class="line"><a name="l00311"></a><span class="lineno">  311</span>&#160;        printf(<span class="stringliteral">&quot;311 child_parent %d\n&quot;</span>, parent-&gt;child.size());</div>
<div class="line"><a name="l00312"></a><span class="lineno">  312</span>&#160;        printf(<span class="stringliteral">&quot;312 v_child_size %d\n&quot;</span>, rs-&gt;child.size());</div>
<div class="line"><a name="l00313"></a><span class="lineno">  313</span>&#160;<span class="preprocessor">#endif</span></div>
<div class="line"><a name="l00314"></a><span class="lineno">  314</span>&#160;        parent-&gt;child.remove(r);</div>
<div class="line"><a name="l00315"></a><span class="lineno">  315</span>&#160;    }</div>
<div class="line"><a name="l00316"></a><span class="lineno">  316</span>&#160;    solveUnderflow(parent);  <span class="comment">//上升一层，如有必要则继续分裂——至多递归O(logn)层</span></div>
<div class="line"><a name="l00317"></a><span class="lineno">  317</span>&#160;}</div>
<div class="line"><a name="l00318"></a><span class="lineno">  318</span>&#160;<span class="preprocessor">#endif</span></div>
</div><!-- fragment --></div><!-- contents -->
<div class="ttc" id="aclassBTree_html"><div class="ttname"><a href="classBTree.html">BTree</a></div><div class="ttdoc">这是B树的实现，内部有一个BTNode作为其结点，BTree实际上就是一个unique_ptr&lt;BTNode&gt; 另外，这个B树是很好的扩展，可以根据传入的T（key）进行不同的处理，只要重载了opera...</div><div class="ttdef"><b>Definition:</b> BTree.h:26</div></div>
<div class="ttc" id="aclassBTree_html_abef4d3b58f15a705a8160360d2cd60ec"><div class="ttname"><a href="classBTree.html#abef4d3b58f15a705a8160360d2cd60ec">BTree::search</a></div><div class="ttdeci">BTNodePosi search(const T &amp;e)</div><div class="ttdoc">搜索值为e的结点，返回其地址，如果搜不到则返回nullptr</div><div class="ttdef"><b>Definition:</b> BTree.h:93</div></div>
<div class="ttc" id="aclassBTree_html_aff6835ad66ba5115ae28b2c21b328f51"><div class="ttname"><a href="classBTree.html#aff6835ad66ba5115ae28b2c21b328f51">BTree::remove</a></div><div class="ttdeci">bool remove(const T &amp;e)</div><div class="ttdoc">从BTree树中删除关键码e 真正删除的节点一定是一个叶子节点，即便e的key不是叶子， 我们也可以通过交换并删除它的后继来达到此效果</div><div class="ttdef"><b>Definition:</b> BTree.h:179</div></div>
<div class="ttc" id="aclassBTree_html_a9fc26aa50dd71d0892fe79a5e4fc7db7"><div class="ttname"><a href="classBTree.html#a9fc26aa50dd71d0892fe79a5e4fc7db7">BTree::BTree</a></div><div class="ttdeci">BTree(int order=3)</div><div class="ttdoc">创建一颗度为order的B树</div><div class="ttdef"><b>Definition:</b> BTree.h:61</div></div>
<div class="ttc" id="aclassBTree_html_ad0a275883210c05d4af1644f45128f18"><div class="ttname"><a href="classBTree.html#ad0a275883210c05d4af1644f45128f18">BTree::insert</a></div><div class="ttdeci">bool insert(const T &amp;e)</div><div class="ttdoc">插入key为e的结点，返回True，</div><div class="ttdef"><b>Definition:</b> BTree.h:115</div></div>
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated by &#160;<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/>
</a> 1.8.17
</small></address>
</body>
</html>
